# ifndef NEWTONFORMULA_H
# define NEWTONFORMULA_H

# include<vector>
# include<iostream>
# include"Polynomial.h"
# include"Function.h"

// 储存牛顿插值的节点信息的结构类
struct node
{
    double x;
    double y;
};

/**
* @brief 定义一个多项式类，能够进行多项式的基本操作
* 
*/
class NewtonFormula
{
private:
    std::vector<struct node> point;  // 储存插值节点信息
    Polynomial poly;                 // 根据节点生成的多项式

    void ComputePol();               // 普通 Newton 插值生成插值多项式
    void HermitePol1(const int & N); // 特殊情况生成 Hermite 插值多项式

public:
    NewtonFormula();                                                                   // 初始化构造函数
    NewtonFormula(const std::vector<struct node> & _point);                            // 根据节点的赋值构造函数
    NewtonFormula(const Function & func, const std::vector<double> & vec);             // 根据函数的构造函数
    NewtonFormula(const int N, const double * X, const double * Y, const double * dY); // 生成 Hermite 插值多项式的构造函数
    ~NewtonFormula() {};                                                               // 析构函数

    double sovle(const double & x) const; // 返回 x 插值多项式计算得到的值
    double diff(const double & x) const;  // 返回插值多项式对 x 的导数值
    void PrintPoint() const;              // 打印节点信息
    void PrintPol() const;                // 打印生成的插值多项式
    void PrintPolCoff() const;            // 从低次到高次打印生成多项式的系数
    Polynomial GetPoly() const;           // 输出生成的插值多项式
    Polynomial GetDiff() const;           // 输出生成多项式的导函数
};

/**
* @brief 普通 Newton 插值生成插值多项式
* 
*/
void NewtonFormula::ComputePol()
{
    std::vector<double> image;
    for (int i = 0; i < point.size(); i++)
    {
        image.push_back(point[i].y);
    }

    for (int j = 1; j < image.size(); j++)
    {
        for (int k = image.size() - 1; k >= j; k--)
        {
            image[k] = (image[k] - image[k-1]) / (point[k].x - point[k-j].x);
        }
    }

    Polynomial p;
    for (int i = point.size() - 1; i > 0; i--)
    {
        std::vector<double> insert{-1 * point[i-1].x, 1};
        Polynomial part(insert);
        p = (p + image[i]) * part;
    }
    poly = p + image[0];
    return;
};

/**
* @brief 特殊情况生成 Hermite 插值多项式
* 
*/
void NewtonFormula::HermitePol1(const int & N)
{
    std::vector<double> image;
    for (int i = 0; i < point.size(); i++)
    {
        image.push_back(point[i].y);
    }

    for (int i = N-1; i > 0; i--)
    {
        image[2*i] = (image[2*i] - image[2*i-2]) / (point[2*i].x - point[2*i-2].x);
    }

    for (int j = 2; j < image.size(); j++)
    {
        for (int k = image.size() - 1; k >= j; k--)
        {
            image[k] = (image[k] - image[k-1]) / (point[k].x - point[k-j].x);
        }
    }

    Polynomial p;
    for (int i = point.size() - 1; i > 0; i--)
    {
        std::vector<double> insert{-1 * point[i-1].x, 1};
        Polynomial part(insert);
        p = (p + image[i]) * part;
    }
    poly = p + image[0];
    return;
};

/**
* @brief 根据节点的赋值构造函数
* 
*/
NewtonFormula::NewtonFormula(const std::vector<struct node> & _point) :
point{_point}
{
    ComputePol();
};

/**
* @brief 根据函数的构造函数
* 
*/
NewtonFormula::NewtonFormula(const Function & func, const std::vector<double> & vec)
{
    for (int i = 0; i < vec.size(); i++)
    {
        struct node part{vec[i], func(vec[i])};
        point.push_back(part);
    }
    ComputePol();
};

/**
* @brief 生成 Hermite 插值多项式的构造函数
* 
*/
NewtonFormula::NewtonFormula(const int N, const double * X, const double * Y, const double * dY)
{
    for (int i = 0; i < N; i++)
    {
        struct node part1{X[i], Y[i]};
        point.push_back(part1);

        struct node part2{X[i], dY[i]};
        point.push_back(part2);
    }
    HermitePol1(N);
};

/**
* @brief 返回 x 插值多项式计算得到的值
* 
*/
double NewtonFormula::sovle(const double & x) const
{
    return poly(x);
};

/**
* @brief 返回插值多项式对 x 的导数值
* 
*/
double NewtonFormula::diff(const double & x) const
{
    return poly.diff(x);
};

/**
* @brief 打印节点信息
* 
*/
void NewtonFormula::PrintPoint() const
{
    for (int i = 0; i < point.size(); i++)
    {
        std::cout << "(" << point[i].x << "," << point[i].y << ") ";
    }
    std::cout << std:: endl;
};

/**
* @brief 打印生成的插值多项式
* 
*/
void NewtonFormula::PrintPol() const
{
    poly.PrintPol();
};

/**
* @brief 从低次到高次打印生成多项式的系数
* 
*/
void NewtonFormula::PrintPolCoff() const
{
    poly.PrintCoff();
};

/**
* @brief 输出生成的插值多项式
* 
*/
Polynomial NewtonFormula::GetPoly() const
{
    return poly;
};

/**
* @brief 输出生成多项式的导函数
* 
*/
Polynomial NewtonFormula::GetDiff() const
{
    return poly.GetDiff();
};

# else
// Do nothing.
# endif